\documentclass[twoside,a4paper]{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}


% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
\usepackage{ctex}%引入中文包
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{float}



\usepackage{listings}
\usepackage{xcolor}      %代码着色宏包
\usepackage{CJK}         %显示中文宏包

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{
 backgroundcolor=\color{lightgray}, 
 basicstyle = \footnotesize,       
 breakatwhitespace = false,        
 breaklines = true,                 
 captionpos = b,                    
 commentstyle = \color{mygreen}\bfseries,
 extendedchars = false,             
 frame =shadowbox, 
 framerule=0.5pt,
 keepspaces=true,
 keywordstyle=\color{blue}\bfseries, % keyword style
 language = C++,                     % the language of code
 otherkeywords={string}, 
 numbers=left, 
 numbersep=5pt,
 numberstyle=\tiny\color{mygray},
 rulecolor=\color{black},         
 showspaces=false,  
 showstringspaces=false, 
 showtabs=false,    
 stepnumber=1,         
 stringstyle=\color{mymauve},        % string literal style
 tabsize=2,          
 title=\lstname                      
}


% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{方丹吟 3190102758}
\chead{二叉搜索树排序的实现}
\rhead{2022.10.18}

\begin{center}
    \LARGE\songti\textbf{二叉搜索树排序的实现} \\%标题
    \large\kaishu\textbf{方丹吟\qquad 3190102758}%一般是我的姓名
\end{center}

\section*{一、主要实现内容}
\begin{itemize}
\item 在课本的 BinaryTree 的代码基础上实现对数组 \_arr 排序的功能。
\end{itemize}

\section*{二、设计}
\subsection*{1.设计思路}

\begin{itemize}
\item 判断用户输入的是否为正常的数组，若用户输入不正确则退出程序；
\item 获取到正确的数组后，首先判断数组是否乱序，乱序则\_mode=1，不乱序则\_mode=0。若\_mode=0，为提高排序效率，应该先对数组 \_arr 乱序后再排序。
\item 排序时依次读入数组中的数，通过insert()函数生成二叉树，再对二叉树进行中序遍历得到有序数组。
\end{itemize}

\subsection*{2.函数代码}
\begin{itemize}
\item BSTSorting函数
\end{itemize}
\begin{lstlisting}[caption={排序函数BSTSorting()}]
    void BSTSorting(std::vector<Comparable> &_arr ,int _mode=0 )
    {
        //首先检验数组_arr是否乱序.
        bool mode = is_sorted( _arr.begin(), _arr.end()) 
                 || is_sorted( _arr.begin(), _arr.end(),greater<int>());
		 //如果乱序，则打乱原数组.
        if (mode == true)
        {
            random_shuffle( _arr.begin(), _arr.end() );
            cout << " The array should be randomized! " << endl;
        }
        else
        {
            cout << " The array is out of order! " << endl;
        }
        
        //遍历vector中的元素，形成二叉树
        typename std::vector<Comparable>::iterator iter;
        BinarySearchTree<Comparable> t;

        for(iter = _arr.begin(); iter != _arr.end(); iter++)
        { t.insert(*iter); }

		//释放内存空间
        _arr.clear();

		//使用中序遍历输出
        t.printTree();  
    };

\end{lstlisting}


\begin{itemize}
\item main()函数
\end{itemize}
\begin{lstlisting}[caption={main.cpp}]
#include <iostream>   
#include <cstdlib>  

#include "binarysearchtree.h"
#include <algorithm> 
#include <fstream> 
#include <vector>
#include <sstream>


using namespace std;

int main()
{
    BinarySearchTree<int> t;
    std::vector<int> _arr;
    std::vector<int> _intarr;

    int mode;
    int k;

    bool correct = true;
    //判断输入的是否为数字
    
	while (k=getchar())
	{
        if(isdigit(k) != 0) 
		   {
            _arr.push_back(k-48);
        }
        else if(k==' '){
            ;
        }
        else if(k=='\n'){
            break;
        }
        else
        {
            correct = false;
            break;
        }
	}
    if(correct == true)
    {
         
        t.BSTSorting(_arr,mode);
    }
    else
    {
        cout << "The type entered is incorrect! " << endl;
    }
    return 0;
}
\end{lstlisting}






%\subsection*{} 

\section*{三、结果报告}
\subsection*{1.测试过程}
\begin{itemize}
\item 输入一个乱序数组[5 3 2 8 1 9 6]
\item 输入一个顺序数组[1 2 3 4 5 6 7]
\item 输入一个倒序数组[7 6 5 4 3 2 1]
\item 错误输入[1 5 3 A B]
\end{itemize}


\subsection*{2.测试结果}



\begin{figure}[H]
     \centering
     \includegraphics{test1}
     \caption{测试1}
\end{figure}

\begin{figure}[H]
     \centering
     \includegraphics{test2}
     \caption{测试2}
\end{figure}

\begin{figure}[H]
     \centering
     \includegraphics{test3}
     \caption{测试3}
\end{figure}

\begin{figure}[H]
     \centering
     \includegraphics{test4}
     \caption{测试4}
\end{figure}



\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
